Міністерство освіти та науки України
НУ „Львівська політехніка”
Лекція №1 4
з курсу: «Застосування засобів об’єктно-орієнтованого програмування в лінгвістичних задачах»
Львів - 2010
11.5. Алгоритм Рабина-Карпа (РК).
Якщо два попередні алгоритми схожі, то цей алгоритм, названий на
честь його розробників, працює за іншою схемою. Розглянемо P і T як
великі числа, записані в системі числення d=256. Кожну букву P[i] і T[i]
вважатимемо «цифрою» від 0 до 255. Тоді P=P[1]dm-1+P[2]dm-2+P[m].
Позначимо Ts=T[s+1]dm-1+T[s+2]dm-2+T[s+m] – частина числа T
завдовжки m d-кових цифр починаючи з зсуву s. Ми шукаємо ті зсуви s, де
Ts=P. Число P можна наперед підрахувати за O(m) ітерацій,
використовуючи схему Горнера: P=P[m]+d(P[m-1]+d(P[m-2]
+....d(P[2]+dP[1])))1. T0 аналогічно обчислюється за O(m) кроків. Далі,
маючи Ts, за O(1) ітерацій можна обчислити Ts+1:Ts+1=(Ts–T[s+1]dm-
1)d+T[s+1+m] («відібравши» старший розряд зліва і «приписавши»
молодший розряд зсправа).
При цьому ми не враховували того, що числа Ts і P настільки великі,
що не помістяться в стандартні типи змінних integer int64 і т.д. Внаслідок
цього доведеться реалізовувати «арифметику з великими числами», де
складність операцій множення, додавання порівняння буде більше, ніж
O(1). Вихід є – виконувати всі обчислення по модулю фіксованого числа q.
Недолік: рівність Ts=P ще незначит, що стрічки P[1..m] і T[s+1..s+m]
рівні, оскільки Ts=P по модулю q. І тому доведеться на кожному кроці
спочатку перевіряти, чи виконується Ts=P, і у випадку позитивного
результату перевіряти посимволам P[1..m]=T[s+1..s+m]. Обчислення
Ts+1 будуть наступними:
Ts+1= d * Ts mod q – h * T[s+1] mod q + T[s+1+m] mod q
1 В.П.Дьяков, Справочник по алгоритмам и програмам, 1987г. стр. 61, Схема Горнера
використовується для обчислення степеневих багаточленів P(Z)(поліномів)
Де h = dm mod q. Основна вимога до вибору q наступне: h d<q. Ця
нерівність необхідна для того, щоб h*T[s+1] < hd неперевищує q.
З першого погляду алгоритм нескладний, але є одна проблема, при
його реалізації з урахуванням буферизированного введення з файлу: треба
завжди пам'ятати m останніх символів тексту T для того, щоб правильно
реалізувати перехід між сусідніми буферами, из-за чого код збільшився
більше, ніж в двох попередніх алгоритмах. Реалізацію з буферизованим
прочитуванням з файлавы можете знайти в RK_buffer.dpr, а для кращого
розуміння матеріалу ми розглянемо код для випадку, коли весь текст
находитсяв пам'яті (RK.dpr):
{$APPTYPE CONSOLE}
program RK;
const
MAXPLEN= 24; { максимальна довжина зразка}
q= 8388593; { максимальне просте число таке, що q*256<2^31-1}
d= 256; { вважаємо, що використовуються всі символи}
var
p: string; { зразок}
n,m: integer; { довжина зразка}
h: integer; {h =d^m mod q}
t:array[1..1048576+1] of char; { весь текст}
p0, t0: integer;
i, s k:integer;
fp,fr:textfile;ft:file; { файлові змінні для зразка, тексту і результату}
begin
assignfile(fp,'p.txt');
reset(fp);
assignfile(ft,'t.txt');
reset(ft, 1);
assignfile(fr,'res_EasyRK.txt');
rewrite(fr);
readln(fp,p);
m :=length(p); { прочитуємо зразок}
n :=FileSize(ft);
blockread(ft, t, n); { і текст}
h := 1;
for i:=1 to m do
h := h*d mod q; {h = d^(m-1) mod q}
p0 := 0; t0 :=0;
for i := 1 to m do
begin
p0:= (d*p0 + byte(p[i])) mod q;
t0:= (d*t0 + byte(t[i])) mod q;
end;
for s := 0 ton-m do
begin
if p0 =t0 then{ якщо передбачається збіг, то}
begin
k:= 1;{ перевіримо, чи співпадають рядки насправді}
while (k<=m) and (p[k]= t[s+k]) do inc(k);
if k>m then { якщо співпадають, то}
writeln(fr,s); { виводимо зсув}
end;
{ обчислюємо наступне Ts}
t0 := ( d * t0 mod q - h * byte(t[s+1]) mod q + byte(t[s+1+m])) mod q; {*}
if t0<0 then t0 := t0 + q; {**}
end;
closefile(fp);
closefile(ft);
closefile(fr);
end.
В якості q беруть найбільше просте число з урахуванням обмежень
qd<231-1 і qh<231-1 для правильності обчислень в рядку, поміченому {*}.
Умова простоти зменшує вірогідніст...
